其他
双向Dijkstra算法
“ Dijkstra算法的进阶版----双向Dijkstra算法。”
Dijkstra算法是一种单向的最短路径算法，有研究者就提出了一种优化方法，即双向Dijkstra算法。其主要思想就是从起点和终点同时开始搜索，这样应该能够提升算法效率。事实证明，在大部分情况下，双向Dijkstra算法还是要优于单向的Dijkstra算法。
01
前面介绍过Dijkstra算法，一些相关的定义可以参考前文。
图的定义以及优先队列的有关定义可以参考前面推送的文章:
(二)最短路径算法--Dijkstra
Dijkstra算法是单点源的形式往外搜索，它的搜索空间长这样：
双向Dijkstra算法顾名思义，就是从两个方向同时开始搜索，它的搜索空间长这样：
从起点和终点同时开始搜索，当两个方向在同一个点相碰时，搜索结束，最短路径也就是s-->x-->t，感觉是有点优势了。
02
Dijkstra算法一个方向搜索需要一个优先队列，那双向Dijkstra算法也就需要两个优先队列了。两个优先队列交替取出最小的元素来扩展，扩展的时候需要检测是否包含环，其扩展过程与Dijkstra算法一样。其原理是从起点和终点依次执行单向的Dijkstra算法，即前向和后向Dijkstra扩展搜索。当两个方向到一个节点相遇时，那么最短路径也就找到了。
03
04
测试部分比较了单向Dijkstra算法和双向Dijkstra算法的效率。随机取了100对OD，分别记录每对OD最短路径计算的运行时间以及扩展节点数量。
为了方便阅读，两幅图中结果都根据Dijkstra算法的测试结果进行了排序。从图中，我们可以很清楚的看到双向Dijkstra的运行时间还是要优于Dijkstra算法的，搜索空间双向Dijkstra算法也是比Dijkstra算法要小。
如需源码，请在后台留言。